package com.zcmyth.tree;

import java.util.Iterator;
import java.util.Stack;

import com.zcmyth.tree.BinaryTree.Node;

public class TreeInOrderIterator<T> implements Iterator<T>{
  
  private final Stack<Node<T>> stack;
  
  public TreeInOrderIterator(BinaryTree<T> tree) {
    this.stack = new Stack<Node<T>>();
    this.stack.push(tree.root());
  }
  
  @Override
  public boolean hasNext() {
    return !stack.empty();
  }

  @Override
  public T next() {
    while(!stack.isEmpty()) {
      Node<T> top = stack.peek();
      if(top.getLeft() != null && !top.getLeft().isVisited()) {
        stack.push(top.getLeft());
      } else {
        stack.pop();
        top.setVisited(true);
        if(top.getRight() != null && !top.getRight().isVisited()) {
          stack.push(top.getRight());
        }
        return top.getData();
      }
    }
    throw new IllegalStateException();
  }

  @Override
  public void remove() {
    throw new UnsupportedOperationException();
  }

}
